package stack_queue.leetcode;

//496. 下一个更大元素 I
//nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
//给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
//对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，
// 并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
//返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Num496 {
    // 单调栈
    private Stack<Integer> stack = new Stack<>();
    // 存储nums2中的每个元素(key)以及他的下一个更大元素值(value)
    private Map<Integer,Integer> map = new HashMap<>();
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 1.扫描nums2，维护单调栈，找到nums2的每个元素的下一个更大元素值
        // 倒着向前遍历是为了正向解决问题 => 向后寻找第一大元素
        for (int i = nums2.length - 1; i >= 0; i--) {
            // 此时栈不为空，且栈顶元素 <= 当前元素
            while (!stack.isEmpty() && stack.peek() <= nums2[i]) {
                stack.pop();
            }
            int nextGreatervalue = stack.isEmpty() ? -1 : stack.peek();
            // 处理完当前元素后，将当前元素压入栈，因为当前元素有可能是前面元素的下一个更大元素
            stack.push(nums2[i]);
            map.put(nums2[i],nextGreatervalue);
        }
        // 再次扫描nums1，取出每个元素对应的value就是结果集
        int[] ret = new int[nums1.length];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = map.get(nums1[i]);
        }
        return ret;
    }
}
